package me.algo.rec;

import com.google.common.collect.Collections2;
import com.google.common.collect.Sets;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author guozheng
 * @date 2024/5/8
 */
public class R1 {

    /**
     * 46. 全排列
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }
        int len = nums.length;
        List<List<Integer>> rtn = new ArrayList<>();
        List<Integer> unused = toList(nums);
        LinkedList<DataRtn> stk = new LinkedList<>();
        DataRtn dataRtn = new DataRtn(new ArrayList<>(len), unused, len);
        stk.addLast(dataRtn);
        while (!stk.isEmpty()) {
            int size = stk.size();
            while (size > 0) {
                size--;
                DataRtn dr = stk.removeFirst();
                List<Integer> uud = dr.unused;
                List<Integer> usd = dr.used;
                for (int i = 0; i < uud.size(); i++) {
                    List<Integer> us = new ArrayList<>(usd);
                    us.addLast(uud.get(i));
                    if (us.size() == dr.len) {
                        rtn.add(us);
                        continue;
                    }
                    List<Integer> ud = new ArrayList<>(uud);
                    ud.remove(i);
                    DataRtn nr = new DataRtn(us, ud, dr.len);
                    stk.addLast(nr);
                }
            }
        }

        return rtn;
    }

    public static List<List<Integer>> permuteUnique(int[] nums) {
        if (Objects.isNull(nums) || nums.length == 0) {
            return new ArrayList<>();
        }
        HashSet<List<Integer>> rtn = new HashSet<>();
        int len = nums.length;
        List<Integer> unused = toList(nums);
        LinkedList<DataRtn> que = new LinkedList<>();
        DataRtn rd = new DataRtn(new ArrayList<>(), unused, len);
        que.addLast(rd);
        while (!que.isEmpty()) {
            int size = que.size();
            while (size > 0) {
                size--;
                DataRtn dataRtn = que.removeFirst();
                List<Integer> used = dataRtn.used;
                List<Integer> dusd = dataRtn.unused;
                for (int i = 0; i < dusd.size(); i++) {
                    List<Integer> usd = new ArrayList<>(used);
                    usd.addLast(dusd.get(i));
                    if (usd.size() == len) {
                        rtn.add(usd);
                        continue;
                    }
                    List<Integer> und = new ArrayList<>(dusd);
                    und.remove(i);
                    DataRtn nxt = new DataRtn(usd, und, len);
                    que.addLast(nxt);
                }
            }
        }
        return new ArrayList<>(rtn);
    }

    record DataRtn(List<Integer> used,List<Integer> unused, int len) {
    }


    private static List<Integer> toList(int[] nums) {
        List<Integer> rtn = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            rtn.add(nums[i]);
        }
        return rtn;
    }


    public static List<List<Integer>> combine(int n, int k) {
        if (n < 1 || k <= 0) {
            return new ArrayList<>();
        }
        List<Integer> dataList = Stream.iterate(1, x -> x + 1).limit(n).toList();
        List<List<Integer>> rtn = new ArrayList<>();
        LinkedList<CombineData> que = new LinkedList<>();
        que.addLast(new CombineData(new ArrayList<>(), dataList));
        while (!que.isEmpty()) {
            int size = que.size();
            while (size > 0) {
                size--;
                CombineData data = que.removeFirst();
                List<Integer> already = data.already();
                Integer max = getMax(already);
                List<Integer> unused = data.unused();
                for (int i = 0; i < unused.size(); i++) {
                    List<Integer> lst = new ArrayList<>(already);
                    Integer ele = unused.get(i);
                    if (ele < max) {
                        continue;
                    }
                    lst.add(ele);
                    if (lst.size() == k) {
                        rtn.add(lst);
                        continue;
                    }
                    List<Integer> unlst = new ArrayList<>(unused);
                    unlst.remove(i);
                    que.add(new CombineData(lst, unlst));
                }
            }
        }
        return rtn;
    }

    private static Integer getMax(List<Integer> already) {
        int lastIdx = already.size() - 1;
        if (lastIdx == -1) {
            return -1;
        }
        Integer max = already.get(lastIdx);
        return max;
    }

    record CombineData(List<Integer> already, List<Integer> unused) {
    }

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> rtn = new ArrayList<>();
        rtn.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            int size = rtn.size();
            for (int j = 0; j < size; j++) {
                List<Integer> na = rtn.get(j);
                List<Integer> nw = new ArrayList<>(na);
                nw.add(nums[i]);
                rtn.add(nw);
            }
        }
        return rtn;
    }

    public static void main(String[] args) {
        List<List<Integer>> subsets = subsets(new int[]{1, 2, 3});
        System.out.println(subsets);
    }
}
